/*
 * Search.cpp
 *
 *  Created on: May 25, 2011
 *      Author: wilsok17
 */

#include "Search.h"
#include <algorithm>
#include <iostream>

Search::Search() {

}

list<pair<string, DIRECTION> > Search::findPath(Grid g, string start, string dest) {
	list<string> white;
	white.push_front(start);
	string parent = start;

	list<pair<string, DIRECTION> > path;
	map<string, pair<string, DIRECTION> > black;

	while (!white.empty()) {
		//remove first item from queue
		string node = white.front();
		white.pop_front();

		//get adjacent nodes
		set<pair<string, DIRECTION> >::iterator i;
		set<pair<string, DIRECTION> > nodes = g.getAdjacent(node);

		//add each adjacent node to the unvisited list
		for (i = nodes.begin(); i != nodes.end(); ++i) {
			//if this is our destination node return the path to it
			if (i->first == dest) {
				//insert this to the map of nodes/parents
				black.insert(pair<string, pair<string, DIRECTION> >(i->first, pair<string, DIRECTION>(node, i->second)));
				path.push_front(pair<string, DIRECTION>(i->first, i->second));
				pair<string, DIRECTION> pathNode = pair<string, DIRECTION>(i->first, i->second);
				//iterate through each node/parent pair until we reach the start
				map<string, pair<string, DIRECTION> >::iterator p;
				p = black.find(pathNode.first);
				while (p != black.end() && p->first != start) {
					pathNode = p->second;
					p = black.find(pathNode.first);
					if(pathNode.first == start) {
						path.push_front(pair<string, DIRECTION>(pathNode.first, START));
					} else {
						path.push_front(pair<string, DIRECTION>(pathNode.first, p->second.second));
					}
				}
				//return the path
				return path;
			}

			//if this node has not been visited, add to the unvisited list
			map<string, pair<string, DIRECTION> >::iterator bi = black.find(i->first);
			if (bi == black.end()) {
				list<string>::iterator wi =
						find(white.begin(), white.end(), i->first);
				if (*wi != i->first) {
					white.push_back(i->first);
				}
			}

			//add node/parent pair to visited nodes map.
			black.insert(pair<string, pair<string, DIRECTION> >(i->first, pair<string, DIRECTION>(node, i->second)));
		}
		parent = node;
	}
	return path;
}

Search::~Search() {

}
